#pragma once

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

namespace TEST
{
	template<class T>
	struct less
	{
		bool operator() (const T& a, const T& b)
		{
			return a < b;
		}
	};

	template<class T>
	struct greater
	{
		bool operator() (const T& a, const T& b)
		{
			return a > b;
		}
	};

	template<class T, class container = vector<T>, class compare = less<T> >
	class priority_queue
	{
	public:
		void adjust_up(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (compare()(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);

					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}

		void adjust_down(int parent)
		{
			int child = parent * 2 + 1;

			while (child < _con.size())
			{
				if (child + 1 < _con.size() && compare()(_con[child], _con[child + 1]))
					++child;

				if (compare()(_con[parent], _con[child]))
				{
					swap(_con[child], _con[parent]);

					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}

		void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size() - 1);
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			adjust_down(0);
		}

		const T& top() const
		{
			return _con.front();
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}
	private:
		container _con;
	};

	void test()
	{
		//cout << less<int>()(1, 2) << endl;

		int a[] = {1, 5, 2, 9, 3, 2, 6};
		int numsSize = sizeof(a) / sizeof(int);

		priority_queue<int, vector<int>, greater<int> > pq;
		for (int i = 0; i < numsSize; i++)
			pq.push(a[i]);

		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}